package 哈希

/*
https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked

128.
最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
*/
func longestConsecutive(nums []int) int {

	m := map[int]bool{}        //创建map
	for _, num := range nums { //遍历数组
		m[num] = true //每个元素都对应true
	}

	maxLen := 0 //声明结果

	for num := range m { //遍历map
		if !m[num-1] { //先判断当前元素是否为序列的起点  即:当前元素-1,是否在map中存在
			curVal := num     //当前元素
			curLen := 1       //以当前元素为起点, 最长连续序列
			for m[curVal+1] { //如果当前元素+1,在map中存在, 连续序列长度+1
				curVal++
				curLen++
			}

			maxLen = max(maxLen, curLen)
		}
	}
	return maxLen
}
